package com.lw.leetcode.stack.b;

import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * 剑指 Offer 59 - II. 队列的最大值
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/31 19:59
 */
public class MaxQueue {

    public static void main(String[] args) {
        MaxQueue test = new MaxQueue();
        test.push_back(1);
        test.push_back(2);
        System.out.println(test.max_value());
        System.out.println(test.a);
        System.out.println(test.b);
        System.out.println(test.pop_front());
        System.out.println(test.a);
        System.out.println(test.b);
        System.out.println(test.max_value());
        System.out.println(test.a);
        System.out.println(test.b);
    }


    LinkedList<Integer> a;
    LinkedList<Integer> b;

    public MaxQueue() {
        a = new LinkedList<>();
        b = new LinkedList<>();
    }

    public int max_value() {
        if (b.isEmpty()) {
            return -1;
        }
        return b.peekFirst();
    }

    public void push_back(int value) {
        a.add(value);
        while (!b.isEmpty() && b.peekLast() < value) {
            b.pollLast();
        }
        b.add(value);
    }

    public int pop_front() {
        if (a.isEmpty()) {
            return -1;
        }
        int v = a.pollFirst();
        if (b.peekFirst() == v) {
            b.pollFirst();
        }
        return v;
    }

}
